1. Field of the Invention
The present invention relates to a method and apparatus for calculating the gradients of texture map parameters in perspective space, and more particularly, to a method and apparatus for calculating the indices to a texture map for all pixels of an input polygon only from the texture map parameters at the vertices of the input polygon and the gradients of the texture map parameters in perspective space.
2. Description of the Prior Art
Texture mapping is a well-known technique for creating more detail and realism in an image without geometrically modeling and rendering every three-dimensional detail of a surface. Simply stated, texture mapping is the process of mapping an image, the texture, onto a three-dimensional surface. A texture can define an object'color, describe the perturbation of surface normals to simulate a bumpy surface, or define the transparency of a surface, but texture mapping also has been applied to a number of other surface attributes such as specularity, illumination, surface displacement and the like. For example, using texture mapping it is possible to simulate the wood grain of a desk top or to model the rough surface of cast iron, thereby greatly improving the realism of the resulting image.
A texture is more particularly defined as a detailed pattern repeated many times to tile a particular plane, as in the wood grain or cast iron example above, or as a multi-dimensional image mapped to a multi-dimensional space. Texture mapping can also be redefined as the mapping of a function onto a surface in three dimensions. The domain of the function can be one, two, or three-dimensional, and it can be represented by either an array or a mathematical function. As used herein, textures will usually be two-dimensional arrays representing a source image (texture) which is mapped onto a surface in three-dimensional object space and which is then mapped to the display screen by the viewing projection. Texture space will be referred to herein by the labels (s,t), although (s,t) is interchangeable with (u,v) as used in the prior art and may thus be referred to as (u,v) as well. Object space (real world coordinates) will be referred to as (x.sub.o, y.sub.o, z.sub.o), while screen space will be referred to as (x,y).
Texture mapping has been used since at least 1974 when Catmull proposed to map textures onto bivariate surface patches. Since then, as noted above, several methods have been proposed for texture mapping parameters such as surface color, specular reflection, normal vector perturbation (bump mapping), specularity, transparency, diffused reflection, shadows, surface displacement, mixing coefficients and local coordinate systems (frame mapping), while yet other methods have provided new techniques for anti-aliasing textured images. However, many of these approaches are very compute-intensive and are thus too slow to be used in an interactive three-dimensional graphics environment.
The mapping from texture space (s,t) to screen space (x,y) may be split into two phases. First, a surface parameterization maps the texture space (s,t) to object space (x.sub.o, y.sub.o, z.sub.o), which is followed by the standard modeling and viewing transformations for mapping object space (x.sub.o, y.sub.o, z.sub.o) to screen space (x,y). Preferably, the viewing transformation is a perspective projection as described in copending application Ser. No. 07/493,189 filed Mar. 14, 1990 assigned to the assignee of this invention and hereby incorporated herein by reference in its entirety. These two mappings are then composed to find the overall two-dimensional texture space to two-dimensional screen space mapping.
As described by Heckbert in "Survey of Texture Mapping," IEEE Computer Graphics and Applications, Vol. 6, No. 11, Nov. 1986, pp. 56-67, there are several general approaches to drawing a texture-mapped surface. Screen order scanning, sometimes called inverse mapping, is the most common method. This method is preferable when the screen must be written sequentially, the mapping is readily invertible and the texture is random access. According to this technique, the pre-image of the pixel in texture space is found for each pixel in screen space and this area is filtered. Texture order scanning, on the other hand, does not require inversion of the mapping as with screen order scanning, but uniform sampling of texture space does not guarantee uniform sampling of screen space except for linear mappings. Thus, for non-linear mappings texture subdivision often must be done adaptively to prevent holes or overlaps in screen space. Finally, two-pass scanning methods may be used to decompose a two-dimensional mapping into two one-dimensional mappings, with the first pass applied to the rows of an image and the second pass applied to the columns of the image. The two-pass methods work particularly well for linear and perspective mappings, where the warps for each pass are linear or rational linear functions. Moreover, because the mapping and filter are one-dimensional, they may be used with graphics pipeline processors. Such techniques are used, for example, for accessing MIP maps as described by Williams in an article entitled "Pyramidal Parametrics," Computer Graphics (Proc. SIGGRAPH 83), Vol. 17, No. 3, Jul. 1984, pp. 213-222.
Mapping a two-dimensional texture onto a surface in three dimensions requires a parameterization of the surface. Heckbert notes that simple polygons such as triangles may be easily parameterized by specifying the texture space coordinates (s,t) at each of its three vertices. This defines a linear mapping between texture space (s,t) and three-dimensional object space (x.sub.o, y.sub.o, z.sub.o), where each of the coordinates in object space has the form As+Bt+C. For polygons with more than three sides, on the other hand, non-linear functions are generally needed. One such non-linear paramerization is the bilinear patch described by Heckbert which maps rectangles to planar or nonplanar quadrilaterals. Planar quadrilaterals may also be parameterized by "perspective mapping", where a homogeneous perspective value W is divided into the x.sub.o, y.sub.o and z.sub.o and z.sub.0 components to calculate the true object space coordinates. An example of a method of perspective mapping is described in detail in the above-mentioned copending application Ser. No. 07/493,189.
After the texture mapping is computed and the texture warped, the image must be resampled on the screen grid. This process is called filtering. The cheapest and simplest texture filtering method is point sampling, where the pixel nearest the desired sample point is used. However, for stretched images the texture pixels are visible as large blocks when this technique is used, and for shrunken images aliasing can cause distracting moire patterns. Such aliasing results when an image signal has unreproducible high frequencies, but aliasing can be reduced by filtering out these high frequencies or by point sampling at a higher resolution. Such techniques are well known for solving the aliasing problem for linear warps; however, for nonlinear warps such as perspective, aliasing has remained a problem. Approximate techniques for reducing aliasing for nonlinear warps are summarized in the aforementioned Heckbert article.
Generally, the nonlinear textures can be prefiltered so that during rendering only a few samples will be accessed for each screen pixel. For example, a color image pyramid (MIP map) as described in the aforementioned Williams article may be used, or preferably, a RIP map, as described in copending application Ser. No. 07/494,706 filed Mar. 16, 1990 assigned to the assignee of this invention and hereby incorporated herein by reference in its entirety, may be used. The texture address into a RIP map is generated using the values s, t, .gradient.s and .gradient.t, for example. Accordingly, the primary requirements for good anti-aliasing is to access texture maps storing prefiltered texture values by determining texture space coordinates (s,t) for each screen pixel plus the partial derivatives of s and t with respect to screen coordinates (x,y).
The partial derivatives (gradients) of the s and t parameters have been calculated in software in prior art devices by calculating the gradients of s and t for all pixels in an input polygon by approximation, based upon a constant value, by linear interpolation of s and t across the polygon, or more accurately by a difference method. For example, in accordance with the difference method, s and t have been calculated from a few points in the vicinity of the pixel and then used to measure the gradients of s and t. However, as noted above, this technique is quite compute intensive and requires the s and t data of numerous adjacent pixels to be stored and several computations to be performed for each pixel. In a parallel processing environment, this need for adjacent s and t values increases the need for inter-processor communication and synchronization. Also, the values of s and t must be quite precise to do a meaningful computation. Moreover, if an input polygon is one pixel in size, the extra sample points have to be taken at sub-pixel resolution to calculate the gradient. Furthermore, sampling of s and t is generally only in the horizontal direction since most prior art hardware is row directed. Thus, this technique works best in the prior art when it is assumed that the gradients of s and t are constant over the polygon so that the gradients need only be calculated once per polygon.
However, for nonlinear mapping, as when perspective interpolation is performed, gradients typically have been calculated on a per pixel basis. In such systems, if the analytical formulas for the partial derivatives (texture gradients) were not available, they were approximated by determining the differences between the s and t values of neighboring pixels. In addition, bump mapping requires additional information at each pixel, namely, two vectors tangent to the surface pointing in the s and t directions. These tangents may be constant across the polygon or may vary, but to ensure artifact-free bump mapping these tangents must be continuous across polygon seams. One way to guarantee this is to compute tangents at all polygon vertices during model preparation and to interpolate them across the polygon. The normal vector is thus computed as the cross product of the tangents. However, such techniques are tedious in that numerous computations must be performed at each pixel and in that the s and t information for neighboring pixels must be kept in memory. As a result, these techniques are relatively slow and thus do not allow for textures to be processed in a user interactive environment.
Thus, texture mapping is a powerful technique for providing visual detail in an image without greatly adding to the complexity of the geometric model. As noted above, algorithms for accessing texture maps and anti-aliasing texture mapped images have existed for a number of years. A more detailed description of these and other prior art texture mapping techniques may be found in the Heckbert article and the extensive bibliography included therein. However, most of the work in the prior art has centered around software solutions which provide excellent image quality but lack the performance required to make this feature useful in an interactive design environment. It is desirable that a hardware system for providing texture mapping for use in graphics pipeline architecture be designed whereby high performance can be attained which permits the resulting graphics system to be user interactive. It is also desirable that true perspective interpolation be performed on the texture parameters so that the resulting image can be displayed in proper perspective and that filtering be done to avoid undesirable aliasing problems.
Accordingly, there is a long-felt need in the art for a graphics display system which can perform gradient interpolation for texture mapping in a user interactive environment for three-dimensional graphics. In particular, there is a long-felt need in the art for a hardware implemented texture mapping system whereby texture map gradients may be accurately interpolated over an input polygon without requiring the use of the s and t data of adjacent pixels of a pixel to be interpolated. The present invention has been designed to meet these needs.